This module is an AA tree implementation for scheme. AA trees are self-balancing binary trees. The module provides non-mutating insert, delete, and search operations, with support for convenient nested tree operations.

Download

http://download.savannah.nongnu.org/releases/guile-aa-tree/

License

GPL-3+ (free software license)

Explanation

“Self-balancing” means that the data structure organizes itself so as to ensure that insert, delete, and search operations never have worse than O(log n) performance. In other words, there is only a few steps in each operation, even when there is a very large number of data nodes. Also, performance is not significantly affected by the order data is entered, or the specific keys chosen.

“Binary trees” means that the structure is made up of linked nodes, which prevents memory fragmentation.

“Non-mutating” means that insert and delete operations create a new tree, rather than modifying or destroying the original tree, meaning that you can still access the old tree provided you keep alive a reference to it. Since trees are nodes linked by references, this is does not waste much space, because nodes that have not changed are shared between the two trees.

“Convenient nested tree operations” means that you can do operations on trees which are stored in the value slot of other tree nodes, by simply passing in a list of keys, instead of a single key. This allows you to treat a tree kind of like a multi-dimensional array. It is actually more convenient and safer, owing to useful built-in behavior:

• The insert operation will create nested trees for you if they don’t already exist.
• The search operation will throw a key-not-found exception if a required nested tree does not exist.
• The delete operation will simply return the original tree if a required nested tree does not exist.